#include <stdio.h>
#include <stdlib.h>

// https://yiyan.baidu.com/chat/NDEwMjMyMzQ3Njo1MDQxNzEwODU2
// 定义二叉树节点结构体
struct TreeNode
{
  int value;
  struct TreeNode *left;
  struct TreeNode *right;
};

// 创建新节点
struct TreeNode *createNode(int value)
{
  struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
  node->value = value;
  node->left = NULL;
  node->right = NULL;
  return node;
}

// 向BST插入节点（递归实现）
struct TreeNode *insert(struct TreeNode *root, int value)
{
  if (root == NULL)
  {
    return createNode(value);
  }
  if (value < root->value)
  {
    root->left = insert(root->left, value);
  }
  else if (value > root->value)
  {
    root->right = insert(root->right, value);
  }
  return root; // 若值已存在，不插入
}

/**
 * @brief 在BST中查找目标值
 * @param root BST的根节点
 * @param target 目标值
 * @return 找到的节点指针，或NULL
 */
struct TreeNode *search_bst(struct TreeNode *root, int target)
{
  if (root == NULL || root->value == target)
  {
    return root;
  }
  if (target < root->value)
  {
    return search_bst(root->left, target);
  }
  else
  {
    return search_bst(root->right, target);
  }
}

int main()
{
  // 构建BST
  struct TreeNode *root = NULL;
  root = insert(root, 50);
  insert(root, 30);
  insert(root, 20);
  insert(root, 40);
  insert(root, 70);
  insert(root, 60);
  insert(root, 80);

  // 测试查找功能
  int targets[] = {60, 90, 20};
  for (int i = 0; i < 3; i++)
  {
    int target = targets[i];
    struct TreeNode *result = search_bst(root, target);
    if (result != NULL)
    {
      printf("找到目标值 %d\n", target);
    }
    else
    {
      printf("未找到目标值 %d\n", target);
    }
  }

  return 0;
}